/*
 * @lc app=leetcode.cn id=399 lang=javascript
 *
 * [399] 除法求值
 */

// @lc code=start
/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
var calcEquation = function (equations, values, queries) {
  let graph = [];
  let visited;
  let i = -1;
  let index = 0;
  const hash = new Map();

  while (++i < equations.length) {
    const [x, y] = equations[i];
    const value = values[i];
    if (!hash.has(x)) hash.set(x, index++);
    if (!hash.has(y)) hash.set(y, index++);

    const idx = hash.get(x);
    const idy = hash.get(y);
    if (!graph[idx]) graph[idx] = [];
    graph[idx][idy] = value;
    if (!graph[idy]) graph[idy] = [];
    graph[idy][idx] = 1 / value;
  }
  visited = new Uint8Array(index);
  return queries.map(([x, y]) => dfs(hash.get(x), hash.get(y)));

  function dfs(x, y) {
    if (!graph[x]) return -1;
    if (graph[x][y]) return graph[x][y];
    for (let i = 0; i < graph[x].length; i++) {
      if (graph[x][i] !== void 0 && visited[i] === 0) {
        visited[i] = 1;
        const res = dfs(i, y);
        visited[i] = 0;
        if (res !== -1) return graph[x][i] * res;
      }
    }
    return -1;
  }
};
// @lc code=end
